package com.mlh.linkedlist;
import java.util.Stack;

//翻转链表
public class 反转链表 {
    //时间复杂度：O(n)
    //空间复杂度：O(n)
    public ListNode method1(ListNode head){
        if(head==null||head.next==null){
            return head;
        }
        //把所有节点压入栈  再弹出
        //使用此方法时，很可能会出现一个错误，且及其难发现
        //错误类型：Error - Found cycle in the ListNode  链表成环
        //为什么会链表循环呢？
        //因为原本链表的头结点 没有和第二个节点断开
        //导致原本的头结点变成尾结点时  他的next不是null  而是原本的第二个节点
        //于是链表就成环了
        Stack<ListNode> stack=new Stack<>();
        ListNode temp=head;
        while(temp!=null){
            stack.push(temp);
            temp=temp.next;
        }
        temp=stack.pop();
        head=temp;
        while (!stack.empty()){
            temp.next=stack.pop();
            temp=temp.next;
        }
        temp.next=null;//最后的尾结点就是原本的头结点 将其next置为空 防止成环
        return head;
    }

    //时间复杂度：O(n)
    // 空间复杂度：O(1)
    public ListNode method2(ListNode head){
        //在遍历链表时，将当前节点的next 指针 改为指向 前一个节点。
        // 由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。
        // 在更改next之前，还需要存储后一个节点。(因为不存储就找不到当前节点的后一个节点，next已改变)
        // 最后返回新的头引用。
        ListNode cur=head;
        ListNode pre=null;
        ListNode next=null;
        while(cur!=null){
            next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }

    public static ListNode practice(ListNode head){
        ListNode next=null,pre=null,cur=null;
        while (head!=null){
            next=head.next;
            head.next=pre;
            pre=head;
            head=next;
        }
        return pre;
    }

}

